<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Binary Search Tree</title>
        <style>
            .node {
                border-radius: 50%;
                font-size: 22px;
                border: 2px solid #000;
                text-align: center;
                line-height: 40px;
            }
            html,
            body {
                width: 100%;
                height: 100%;
            }
            .edge {
                /* background: #000; */
                width: 1000%;
                height: 200%;
            }
        </style>
    </head>
    <body>
        <div class="wrap"></div>
        <svg class="edge"></svg>
        <script>
            class Node {
                constructor(element) {
                    this.element = element;
                    this.left = null;
                    this.right = null;
                    this.position = {
                        left: 0,
                        top: 0,
                    };
                }
            }
            class BinarySearchTree {
                constructor() {
                    this.root = null;
                    this.nodeSize = 40;
                    this.distance = 60;
                    this.maxLevel = 0;
                    this.container = document.querySelector(".wrap");
                    this.containerTimeout = 0;
                    this.edgeContainer = document.querySelector(".edge");
                    this.edgeTimout = 0;
                }
                insert(element) {
                    let node = new Node(element);
                    if (this.root === null) {
                        node.position.left = (window.innerWidth + 1000) / 2;
                        node.position.top = 100;
                        this.root = node;
                        this.drawNode(node);
                    } else {
                        this.insertNode(this.root, node);
                    }
                }
                insertNode(insertNode, node, level = 1) {
                    if (insertNode.element > node.element) {
                        if (insertNode.left === null) {
                            node.position.top =
                                insertNode.position.top + this.distance;
                            insertNode.left = node;
                            if (level > this.maxLevel) {
                                this.maxLevel = level;
                            }
                            this.drawNode(node);
                            this.drawLine(insertNode, node, "left");
                        } else {
                            this.insertNode(insertNode.left, node, level + 1);
                        }
                    } else if (insertNode.element < node.element) {
                        if (insertNode.right === null) {
                            node.position.top =
                                insertNode.position.top + this.distance;
                            insertNode.right = node;
                            if (level > this.maxLevel) {
                                this.maxLevel = level;
                            }
                            this.drawNode(node);
                            this.drawLine(insertNode, node, "right");
                        } else {
                            this.insertNode(insertNode.right, node, level + 1);
                        }
                    }
                }
                calcuNode(node = this.root, level = 1) {
                    // 计算当前节点的位置
                    if (node.left) {
                        node.left.position.left =
                            node.position.left -
                            Math.floor(
                                this.distance *
                                    Math.pow(2, this.maxLevel - level - 1)
                            );
                        this.calcuNode(node.left, level + 1);
                    }
                    if (node.right) {
                        node.right.position.left =
                            node.position.left +
                            Math.floor(
                                this.distance *
                                    Math.pow(2, this.maxLevel - level - 1)
                            );
                        this.calcuNode(node.right, level + 1);
                    }
                }
                search(element) {
                    return this.searchNode(this.root, element);
                }
                searchNode(node, element) {
                    if (node === null) {
                        return false;
                    }

                    if (node.element === element) {
                        return true;
                    } else if (node.element > element) {
                        return this.searchNode(node.left, element);
                    } else if (node.element < element) {
                        return this.searchNode(node.right, element);
                    }
                }
                preTraverse(callback) {
                    this.preTraverseNode(this.root, callback);
                }
                preTraverseNode(node, callback) {
                    if (node !== null) {
                        this.preTraverseNode(node.left, callback);
                        callback(node);
                        this.preTraverseNode(node.right, callback);
                    }
                }
                inOrderTraverse(callback) {
                    this.inOrderTraverseNode(this.root, callback);
                }
                inOrderTraverseNode(node, callback) {
                    if (node !== null) {
                        callback(node);
                        this.inOrderTraverseNode(node.left, callback);
                        this.inOrderTraverseNode(node.right, callback);
                    }
                }
                nextTraverse(callback) {
                    this.nextTraverseNode(this.root, callback);
                }
                nextTraverseNode(node, callback) {
                    if (node !== null) {
                        this.nextTraverseNode(node.right, callback);
                        callback(node);
                        this.nextTraverseNode(node.left, callback);
                    }
                }
                max() {
                    let current = this.root;
                    while (current && current.right !== null) {
                        current = current.right;
                    }
                    return current;
                }
                min() {
                    let current = this.root;
                    while (current && current.left !== null) {
                        current = current.left;
                    }
                    return current;
                }
                drawNode(node) {
                    setTimeout(() => {
                        let ele = document.createElement("span");
                        ele.style.position = "absolute";
                        ele.style.width = this.nodeSize + "px";
                        ele.style.height = this.nodeSize + "px";
                        ele.style.left = node.position.left + "px";
                        ele.style.top = node.position.top + "px";
                        ele.textContent = node.element;
                        ele.className = "node";
                        this.container.appendChild(ele);
                    }, this.containerTimeout++ * 1000);
                }
                drawLine(from, to, dir) {
                    setTimeout(() => {
                        this.edgeContainer.innerHTML += `<line x1="${
                            from.position.left + 15
                        }" y1="${from.position.top + 35}" x2="${
                            dir == "left"
                                ? to.position.left + 30
                                : to.position.left
                        }" y2="${
                            to.position.top
                        }" style="stroke:rgb(255,0,0);stroke-width:2" />`;
                    }, this.edgeTimout++ * 1000);
                }
            }
            let array = [];
            for (let i = 0; i < 10; i++) {
                array.push(i);
            }
            array.sort(() => Math.random() - 0.5);
            // 创建二叉树
            let bst = new BinarySearchTree();
            for (let i = 0; i < array.length; i++) {
                bst.insert(array[i]);
                // debugger;
            }
            // 计算距离
            bst.calcuNode();
            console.log("bst...", bst, bst.max(), bst.min(), bst.maxLevel);
            // 查找二叉树
            let result = bst.search(90);
            console.log("result...", result);
            // 先序遍历
            // bst.preTraverse(node=>{
            //   console.log('先序遍历...', node.element);
            // })
            // 先序遍历
            // bst.inOrderTraverse(node=>{
            //   console.log('中序遍历...', node.element);
            // })
            // 后序遍历
            bst.nextTraverse((node) => {
                console.log("后序遍历...", node.element);
            });
        </script>
    </body>
</html>
